package com.zwy.leetcode;

import java.util.*;

public class Day09Test {
    /**
     * 16. 最接近的三数之和
     * @param nums
     * @param target
     * @return
     */
    public int min;
    public int count=0;
    public int res=0;
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        min=2147483647;
        LinkedList<Integer>list=new LinkedList<Integer>();
        backTrack(nums,target,list,0);
        System.out.println(min);
        return res;
    }

    public void backTrack(int []nums,int target,LinkedList<Integer> list,int start){
        if(list.size()==3){
            if(Math.abs(count-target)<min){
                res=count;
            }
            min=Math.min(Math.abs(count-target),min);
            return;
        }
        for (int i = start; i <nums.length ; i++) {
            if(list.contains(i))continue;
//            if(list.size()<=2&&Math.abs(count-target)>min)return;
//            if(list.size()==2&&Math.abs(count+nums[i]-target)>min)return;
            list.add(i);
            count+=nums[i];
            backTrack(nums,target,list,i+1);
            list.removeLast();
            count-=nums[i];
        }
    }

    /**
     * 22. 括号生成
     * @param n
     * @return
     */
    List<String> res1=new LinkedList<String>();
    String s="";
    public List<String> generateParenthesis(int n) {
            LinkedList<Integer>list=new LinkedList<Integer>();
        LinkedList<Character>list0=new LinkedList<Character>();
        char[] chars=new char[n*2];
        for (int i = 0; i < n*2; i++) {
            if(i<n)chars[i]='(';
            else chars[i]=')';
        }
        backTrack1(chars,list,list0);

        Set<String>set=new HashSet<String>(res1);
        res1.clear();
        res1.addAll(set);
        return res1;
    }
    public void backTrack1(char[]chars, LinkedList<Integer>list,LinkedList<Character>list0){
        Character[] objects = (Character[])list0.toArray(new Character[list0.size()]);
        if(list.size()==chars.length){
            char []str=new char[list.size()];

            for (int i = 0; i < list.size(); i++) {
                str[i]=list0.get(i);
            }
            boolean valid = isValid(str);
            if(valid)
            res1.add(new String(str));
            return;
        }
        for (int i = 0; i <chars.length ; i++) {
            if(list.contains(i))continue;
            if(list.size()==chars.length-1&&chars[i]=='(')return;
            if(list.size()==0&&chars[i]==')')return;
            if(objects.length>=3&&objects[1]==')'&&objects[2]==')')return;
            if(chars.length>=4&&objects.length==chars.length-1&&objects[chars.length-3]=='('&&objects[chars.length-2]=='(')return;

            list.add(i);
            list0.add(chars[i]);
            backTrack1(chars,list,list0);
            list.removeLast();
            list0.removeLast();
        }
    }
    public boolean isValid(char []str){
        Stack<Character>stack = new Stack<Character>();
        for(char c: str){
            if(c=='(')stack.push(')');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        int[]arr={ 1,1,1,0};
        int target=100;
        Day09Test test=new Day09Test();
        test.generateParenthesis(3);
    }
}
